'''
字符串匹配
KMP python版
28.实现strStr()
459.重复的子字符串
'''

from typing import List

class Solution:
    def getNext(self, pattern: str, next: List[int]) -> None:
        j = -1
        next[0] = -1
        i = 0
        while i < len(pattern):
            if j == -1:
                i += 1
                j += 1
            elif pattern[i] == pattern[j]:
                i += 1
                j += 1
                next[i] = j
            else:
                j = next[j]
    
    # 匹配到第一个就退出
    def kmpSearch(self, text: str, pattern: str) -> int:
        i, j = 0, 0
        next = [0] * len(pattern)
        self.getNext(pattern, next)
        while i < len(text) and j < len(pattern):
            if j == -1 or text[i] == pattern[j]:
                i += 1
                j += 1
            else:
                j = next[j]
        if j == len(pattern):
            return i - j
        return -1

    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)

    def repeatedSubstringPattern(self, s: str) -> bool:
        # 若s有重复子串，则至少两次
        # s+s则至少四次，去除首位元素，即人为破坏两次，还剩至少两次
        # 若s无重复子串，则s+s破坏两次后不再含s
        return True if (s + s).find(s, 1, 2 * len(s) - 1) != -1 else False

solve = Solution()

s = 'abababcd'
t = 'abcd'
print(solve.kmpSearch(s, t))